【LeetCode 3】Longest Substring Without Repeating Characters 无重复字符的最长子串

发表于 | 分类于

[LeetCode 3]Longest Substring Without Repeating Characters 无重复字符的最长子串

Problem description:

Given a string, find the length of the longest substring without repeating characters.

Example:

1
2
3
4
5
Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

问题描述:

给定一个字符串，找出不含有重复字符的最长子串的长度。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。

给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。

给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。

Solution:

Solution 1: 遍历char数组，put到map<字符，字符下标>中，若当前元素在map中，则将下表置为当前元素在map中的重复值的角标+1,继续遍历，复杂度O(N2)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//beat 18%
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals(""))
            return 0;
        HashMap<Character,Integer> map=new HashMap<>();
        char []array=s.toCharArray();
        int max=1;
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                max=max>map.size()?max:map.size();
                i=map.get(array[i]);
                map.clear();
            }else{
                map.put(array[i],i);
            }          
        }
        max=max>map.size()?max:map.size();
        return max;
    }
}

Solution 2：（优化的滑动窗口）
(i,j)作为一个窗口，让j滑动，并将j位置的字符放到map中，当map包含j位置的字符时,(未优化的滑动窗口是让i滑动，直到i，j不包含重复字符串)，i取map中j字符所在位置+1和i的最大值（考虑baab字符串，就明白为什么i取两者之间的大者），向hashmap添加重复元素时会覆盖原来的值。时间复杂度为O(n)。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//beat 67%
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals(""))
            return 0;
        HashMap<Character,Integer> map=new HashMap<>();
        int max=1;
        int n=s.length();
        for(int i=0,j=0;j<n;j++){
            if(map.containsKey(s.charAt(j))){
                i=Math.max(map.get(s.charAt(j))+1,i);
            }
            max=Math.max(max,j-i+1);
            map.put(s.charAt(j),j);
        }
        return max;
    }
}
Thanks!